package 中等.二分查找;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;


/**
 * 给你一个正整数数组 nums 。
 * 同时给你一个长度为 m 的整数数组 queries 。第 i 个查询中，你需要将 nums 
 * 中所有元素变成 queries[i] 。你可以执行以下操作 任意 次：
 * 将数组里一个元素 增大 或者 减小 1 。
 * 请你返回一个长度为 m 的数组 answer ，其中 answer[i]是将 nums 中所有元
 * 素变成 queries[i] 的 最少 操作次数。
 * 注意，每次查询后，数组变回最开始的值。
 * <p>
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode.cn/problems/minimum-operations-to-make-all-array-elements-equal
 */
public class 使数组元素全部相等的最少操作次数_2602 {

    public static void main(String[] args) {

    }

    /**
     * 排序+二分查找+前缀和+分类讨论
     * 排序不影响最终结果，排序后二分查找 > queries[i] 的第一个数 nums[mid]
     * [0,mid-1] 每个数都要 + 的操作变成 queries[i] ，[mid,end] 每个数
     * 都要 - 的操作变成 queries[i]
     * ans[i] = queries[i]*(mid-1-0+1) - prefixSum[mid-1] +
     * prefixSum[end] - prefixSum[mid-1] - queries[i]*(end-mid+1)
     * 注意：prefixSum[i] 这里用的是索引，而实际操作中用的是第几个元素
     */
    public List<Long> minOperations(int[] nums, int[] queries) {
        List<Long> list = new ArrayList<>();
        Arrays.sort(nums);
        long[] prefixSum = new long[nums.length + 1];
        for (int i = 0; i < nums.length; i++) {
            prefixSum[i + 1] = prefixSum[i] + nums[i];
        }

        // 注意 int 溢出
        for (int i = 0; i < queries.length; i++) {
            int mid = binarySearch(nums, queries[i]);
            long curSum = 0;
            if (mid == -1) {
                curSum += (long) queries[i] * nums.length - prefixSum[nums.length];
            } else {
                curSum += (long) queries[i] * mid - prefixSum[mid];
                curSum += prefixSum[nums.length] - prefixSum[mid] - (long) queries[i] * (nums.length - mid);
            }
            list.add(curSum);
        }
        return list;
    }

    private int binarySearch(int[] nums, int target) {
        int ans = -1;
        int left = 0, right = nums.length - 1;
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] > target) {
                ans = mid;
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }
        return ans;
    }

}
